package tree;

import java.util.*;

import org.junit.Test;

import array.Ex253.Solution;

public class Ex297 {
    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
    public class Codec1 { //层序遍历解决 即BFS方法

        // Encodes a tree to a single string.
        //还是不知道到底应该多少个值。。。
        public String serialize1(TreeNode root) {
            if (root == null) return "[]";
            int c = getCount(root, 0);
            String[] res = new String[c];
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode cur;
            res[0] = "" + root.val;
            int idx = 0, left , right, len = res.length;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if ((left = idx * 2 + 1) < len) {
                    if (cur.left != null) {
                        res[left] = cur.left.val + "";
                        queue.offer(cur.left);
                    } else {
                        res[left] = "null";
                    }
                }
                if ((right = idx * 2 + 2) < len) {
                    if (cur.right != null) {
                        res[right] = cur.right.val + "";
                        queue.offer(cur.right);
                    } else {
                        res[right] = "null";
                    }
                }
                idx++;
            }

            StringBuilder sb = new StringBuilder("[");
            for (int i = 0; i < res.length; i++) {
                sb.append(res[i] + ", ");
            }
            String result = sb.substring(0, sb.length() - 2);
            result += "]";
            return result;
        }
        
        public int getCount(TreeNode root, int cur) {
            if (root == null) return cur;
            cur++;
            cur += getCount(root.left,cur);
            cur += getCount(root.right, cur);
            return cur;
        }


        public String serialize(TreeNode root) {
            if (root == null) return "[]";
            StringBuffer sb = new StringBuffer("[");
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            TreeNode cur = root;
            // sb.append(cur.val + ", ");
            int h = getHeight(root), idx = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    cur = queue.poll();
                    if (cur == null) {
                        sb.append("null,");
                    } else {
                        sb.append(cur.val + ",");
                        queue.offer(cur.left);
                        queue.offer(cur.right);
                    }
                }
                idx++;
                if (idx == h) break;
            }
            sb.delete(sb.length() - 1, sb.length());
            sb.append("]");
            return sb.toString();
        }

        public int getHeight(TreeNode root) {
            if (root == null) return 0;
            int l = getHeight(root.left);
            int r = getHeight(root.right);
            return Math.max(l, r) + 1;
        }


        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if ("[]".equals(data)) return null;
            data = data.substring(1, data.length() - 1);
            String t[] = data.split(",");
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(t[0]));
            queue.offer(root);
            TreeNode cur = root;
            
            int idx = 1, l, r, len = t.length;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if ((l = idx * 2 + 1) < len && !"null".equals(t[l])) {
                    cur.left = new TreeNode(Integer.parseInt(t[l]));
                    queue.offer(cur.left);
                }
                if ((r = idx * 2 + 2) < len && !"null".equals(t[r])) {
                    cur.right = new TreeNode(Integer.parseInt(t[r]));
                    queue.offer(cur.right);
                }
                idx++;
                if (idx == len) break;
            }

            return root;
        }
    }

    @Test
    public void test() {
        Integer[] tree = new Integer[] {1,2,3,null,null,4,5};
        TreeNode root = TreeUtils.createTree(tree);
        Codec codec = new Codec();
        // System.out.println(codec.getCount(root, 0));
        System.out.println(codec.serialize(root));
    }

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));


public class Codec { //前序遍历 即深度遍历方法


    /* 
    1,2,null,null,3,4,null,null,5,null,null
    变成这样，真的有应用价值吗。。。
    */
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        return dfs(root);
    }

    public String dfs(TreeNode root) {
        if (root == null) return "null";
        String left = dfs(root.left), right = dfs(root.right);
        return root.val + "," + left + "," + right;
    }

    // Decodes your encoded data to tree.

    /* 
        因为编码是按照前序来的，反编码也需要按照前序来
    */
    public TreeNode deserialize(String data) {
        System.out.println(data);
        if ("[]".equals(data)) return null;
        Deque<String> deque = new LinkedList<>();
        for (String s: data.split(",")) {
            deque.offerLast(s);
        }
        return toTree(deque);
    }

    public TreeNode toTree(Deque<String> deque) {
        if (deque.isEmpty()) return null;
        String cur = deque.pollFirst();
        if ("null".equals(cur)) return null;
        TreeNode r = new TreeNode(Integer.parseInt(cur));
        r.left = toTree(deque);
        r.right = toTree(deque);
        return r;
    }
}

@Test
public void test2() {

    Integer[] tree = new Integer[] {1,2,3,null,null,4,5};
    TreeNode root = TreeUtils.createTree(tree);
    Codec codec1 = new Codec();
    codec1.deserialize(codec1.serialize(root));
}

}
